package problems.practice;

import java.util.ArrayList;
import java.util.List;

/**
 * 658. 找到 K 个最接近的元素
 * <p>https://leetcode.cn/problems/find-k-closest-elements/</p>
 *
 * @author habitplus
 * @since 2022/9/29 09:30
 */
public class T658 {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        int n = arr.length;
        int pos = partition(arr, x);

        int l = pos - 1;
        int r = pos;
        while (k-- > 0) {
            if (r >= n) --l;
            else if (l < 0) ++r;
            else {
                if (x - arr[l] <= arr[r] - x) --l;
                else ++r;
            }
        }

        List<Integer> list = new ArrayList<>();
        while (l + 1 < r) {
            list.add(arr[++l]);
        }

        return list;

    }

    /**
     * 寻找分区点
     * [0, l) < x, [l, n) >= x
     */
    private int partition(int[] arr, int x) {
        int mid;
        int l = 0;
        int r = arr.length - 1;
        while (l < r) {
            mid = l + (r - l) / 2;
            if (arr[mid] < x) l = mid + 1;
            else r = mid;
        }

        return l;
    }
}
